package datastructure.map;

import java.util.Objects;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/4/27 02:47
 */
public class LinkedHashMap<K, V> extends HashMap<K, V> {
    private LinkedNode<K, V> first;
    private LinkedNode<K, V> last;

    @Override
    public void clear() {
        super.clear();
        first = null;
        last = null;
    }

    @Override
    protected void afterRemove(Node<K, V> willNode, Node<K, V> removedNode) {

        LinkedNode<K, V> linkedWillNode = (LinkedNode<K, V>) removedNode;
        LinkedNode<K, V> linkedRemovedNode = (LinkedNode<K, V>) removedNode;

        if (willNode != removedNode) {
            // 交换willNode和removedNode在链表中的位置
            LinkedNode<K, V> tempPrev = linkedWillNode.prev;
            LinkedNode<K, V> tempNext = linkedWillNode.next;
            linkedWillNode.prev = linkedRemovedNode.prev;
            linkedWillNode.next = linkedRemovedNode.next;
            linkedRemovedNode.prev = tempPrev;
            linkedRemovedNode.next = tempNext;
            // 交换后，如果linkedWillNode.prev == null，说明linkedWillNode是头结点
            if (linkedWillNode.prev == null) {
                first = linkedWillNode;
            } else {
                linkedWillNode.prev.next = linkedWillNode;
            }

            // 交换后，如果linkedWillNode.next == null，说明linkedWillNode是尾结点
            if (linkedWillNode.next == null) {
                last = linkedWillNode;
            } else {
                linkedWillNode.next.prev = linkedWillNode;
            }
        }

        LinkedNode<K, V> prev = linkedWillNode.prev;
        LinkedNode<K, V> next = linkedWillNode.next;
        if (prev == null) { // 删除的是头结点
            first = next;
        } else {
            prev.next = next;
        }
        if (next == null) { // 删除的是尾结点
            last = prev;
        } else {
            next.prev = prev;
        }
        super.afterRemove(willNode, removedNode);
    }

    @Override
    public boolean containsValue(Object value) {
        LinkedNode<K, V> node = first;
        while (node != null) {
            if (Objects.equals(value, node.value)) return true;
            node = node.next;
        }
        return false;
    }



    @Override
    protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
        LinkedNode<K, V> node = new LinkedNode<>(key, value, parent);
        if (first != null) {
            node.next = first;
            first.prev = node;
        }
        first = node;
        return node;
    } //

    @Override
    public void traversal(Visitor visitor) {
        if (visitor == null) return;
        LinkedNode<K, V> node = first;
        while (node != null) {
            if (visitor.visit(node.key, node.value)) return;
            node = node.next;
        }
    }

    private static class LinkedNode<K, V> extends Node<K, V> {
        LinkedNode<K, V> prev;
        LinkedNode<K, V> next;

        public LinkedNode(K key, V value, Node<K, V> parent) {
            super(key, value, parent);
        }
    }
}
